# 39. 组合总和
# 给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。你
# 可以按任意顺序返回这些组合。
# candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
# 对于给定的输入，保证和为target的不同组合数少于150个。
#
# 示例1：
# 输入：candidates=[2,3,6,7],target=7
# 输出：[[2,2,3],[7]]
# 解释：
# 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
# 7 也是一个候选， 7 = 7 。
# 仅有这两种组合。
#
# 示例2：
# 输入: candidates = [2,3,5], target = 8
# 输出: [[2,2,2,2],[2,3,3],[3,5]]
# 示例 3：
#
# 输入: candidates = [2], target = 1
# 输出: []


class Solution:
    def combinationSum(self, candidates: [int], target: int):
        # 直接看的C的参考
        res = []
        path = []
        candidates.sort()
        tmp = []
        for i in candidates:
            if i <= target:
                tmp.append(i)

        def backtracking(candidates, target, su, startindex):
            if su > target:
                return
            if su == target:
                res.append(path[:])
                return
            size = len(candidates)
            for i in range(startindex, size):
                su += candidates[i]
                path.append(candidates[i])
                backtracking(candidates, target, su, i)
                su -= candidates[i]
                path.pop()

        backtracking(tmp, target, 0, 0)
        return res

    def combinationSum2(self, candidates: [int], target: int):
        # 自己做的
        res = []
        path = []
        tmp = []
        for i in candidates:
            if i <= target:
                tmp.append(i) # 这里算是剪枝操作

        def backtracking(candidates, target, index):
            if sum(path) > target:
                return
            if sum(path) == target:
                res.append(path[:])
                return
            size = len(candidates)
            for i in range(index, size):
                path.append(candidates[i])
                backtracking(candidates, target, i)
                path.pop()

        backtracking(tmp, target, 0)
        return res

    # 下面是代码随想录的python答案
    def __init__(self):
        self.path = []
        self.paths = []

    def combinationSum(self, candidates: [int], target: int):
        '''
        因为本题没有组合数量限制，所以只要元素总和大于target就算结束
        '''
        self.path.clear()
        self.paths.clear()

        # 为了剪枝需要提前进行排序
        candidates.sort()
        self.backtracking(candidates, target, 0, 0)
        return self.paths

    def backtracking(self, candidates: [int], target: int, sum_: int, start_index: int) -> None:
        # Base Case
        if sum_ == target:
            self.paths.append(self.path[:])  # 因为是shallow copy，所以不能直接传入self.path
            return
        # 单层递归逻辑
        # 如果本层 sum + condidates[i] > target，就提前结束遍历，剪枝
        for i in range(start_index, len(candidates)):
            if sum_ + candidates[i] > target:
                return
            sum_ += candidates[i]
            self.path.append(candidates[i])
            self.backtracking(candidates, target, sum_, i)  # 因为无限制重复选取，所以不是i-1
            sum_ -= candidates[i]  # 回溯
            self.path.pop()  # 回溯


if __name__ == '__main__':
    candidates = [2, 3, 6, 7]
    target = 7
    # candidates = [10, 1, 2, 7, 6,5]
    # target = 8
    tmp = Solution()
    res = tmp.combinationSum(candidates, target)
    print(res)
